package cn.lishiyuan.algorithm.sort;

import java.util.List;

/**
 * 堆排序（大顶堆）
 * <br>
 * 堆排序分两步，建堆，然后堆排序
 * 建堆，堆顶元素就是最大元素
 * 堆排序，将堆顶元素置换到末尾，再对n-1个元素进行堆化，依次类推，最终就能获得有序列表
 */
public class HeapSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {
        throw new UnsupportedOperationException("sort is not implemented yet");
    }

    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {
        int size = data.length;

        // 从最后一个非叶子节点开始堆化
        for (int i = (size - 1) / 2; i >= 0; i--) {
            // 堆化i -> size 元素
            heapify(data,size,i);
        }

        for (int i = size - 1; i > 0; i--) {
            // 将最后的元素交换到最后一个位置
            T temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            // 堆化
            heapify(data,i,0);
        }

        return data;
    }

    private <T extends Comparable<T>> void heapify(T[] data,int size, int index){
        // 从该index进行自上而下的堆化
        /**
         *        [a1]
         *       /  \
         *   [b2]   [c3]
         *   /\      /\
         *[d4][e5][e6][f7]
         *
         * ```
         * index(L) = index(E) * 2 + 1
         * index(R) = index(E) * 2 + 2
         * index(P) = (index(E) - 1) / 2
         * ```
         */
        // 大顶堆
        // 与每一层的子节点比较大小，找出大的那个与其交换位置
        while (true){
            int maxIndex = index;
            int lIndex = index * 2 + 1;
            int rIndex = index * 2 + 2;

            if(lIndex < size && data[lIndex].compareTo(data[maxIndex]) > 0){
                // 左节点比较大
                maxIndex = lIndex;
            }

            if(rIndex < size && data[rIndex].compareTo(data[maxIndex]) > 0){
                // 右节点比较大
                maxIndex = rIndex;
            }

            if(maxIndex == index){
                // 当前节点不比任何节点大了
                return;
            }
            T temp = data[index];
            data[index] = data[maxIndex];
            data[maxIndex] = temp;
            index = maxIndex;
        }
    }
}
